
package code;

import java.util.Stack;

public class Solution {
	
	static class RandomListNode{
		int label;
		RandomListNode next;
		RandomListNode random;
		RandomListNode(int x){
			label=x;
		}
	}
	
	private Stack<Integer> sck=new Stack();
	
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode cloneHead,p,q;
        q=cloneHead=null;
        
        sck.push(1);
        sck.pop();
        
        //
        int i=0;
        for(p=head;p!=null;){
        	RandomListNode rln=new RandomListNode(p.label);
        	rln.next=p.next;
        	q=p;
        	p.next=rln;
        	p=p.next.next;
        }
        //����randomָ��Ķ���
        for(p=head;p!=null;){
        	q=p.next;
        	if(p.random!=null)
        		q.random=p.random.next;
        	
        	p=p.next.next;
        }
        cloneHead=head.next;
        for(p=head.next;p!=null;){
        	if(p.next!=null)
        		p.next=p.next.next;
        	p=p.next;
        }
        return cloneHead;
    }
    
    public static void main(String[] args){
    	RandomListNode head=new RandomListNode(-1);
    	Solution solution=new Solution();
    	solution.copyRandomList(head);
    }
}
